
#pragma once

#include <vector>

class Solution33
{
public:
	int search(const std::vector<int>& nums, int target)
	{
		int first = 0, last = (int)nums.size();
		while (first != last)
		{
			const int mid = first + (last - first) / 2;
			if (nums[mid] == target)
				return mid;
			if (nums[first] <= nums[mid])
			{
				if (nums[first] <= target && target < nums[mid])
					last = mid;
				else
					first = mid + 1;
			} 
			else
			{
				if (nums[mid] < target && target <= nums[last - 1])
					first = mid + 1;
				else
					last = mid;
			}
		}
		return -1;
	}
};

class Solution81
{
public:
	bool search(const std::vector<int>& nums, int target)
	{
		int first = 0, last = (int)nums.size();
		while (first != last)
		{
			const int mid = first + (last - first) / 2;
			if (nums[mid] == target)
				return true;
			if (nums[first] < nums[mid])
			{
				if (nums[first] <= target && target < nums[mid])
					last = mid;
				else
					first = mid + 1;
			}
			else if (nums[first] > nums[mid])
			{
				if (nums[mid] < target && target <= nums[last - 1])
					first = mid + 1;
				else
					last = mid;
			}
			else // =
			{
				first++;
			}
		}
		return false;
	}
};